package com.frx.leetoffer.recall;

import java.util.Arrays;

/**
 * @author ：frx
 * @date ：Created in 2019/11/3 18:12
 * @description： 八皇后问题
 * @modified By：
 * @version: ToDO
 */
public class QueenEight {

    /** 下标表示行，值表示queue存储在哪一列*/
    private static int[] result = new int[8];
    public static void main(String[] args){
        eightQueues(0);
        // System.out.println(Arrays.toString(result));
        /*printQueens(result);*/
    }
    public static void eightQueues(int row){
        if (row == 8){
            printQueens(result);
            System.out.println(Arrays.toString(result));
            return;
            // 8行棋子都放好了 无需再递归了
        }

        for (int column=0;column<8;column++){
            // 检验放法是否满足
            if (isOk(row,column)){
                // 满足的话将棋子放到第row行第column列
                result[row] = column;
                // 考察下一行
                eightQueues(row+1);
            }
        }

    }

    /**
     * @description 判断row行column列放棋子是否合适
     * @param row
     * @param column
     * @return
     */
    private static boolean isOk(int row,int column){

        int leftUp = column -1;
        int rightUp = column + 1;
        // 逐层往上考察每一行
        for (int i=row -1;i>=0;i--){
            // 考察上方
            if (result[i] == column){
                return false;
            }
            if (leftUp >= 0 && result[i] == leftUp){
                // 考察左对角线 第i行leftUp是否有棋子
                return false;
            }
            if (rightUp < 8 && result[i] == rightUp){
                // 考察右对角线 第i行 rightUp是否有棋子
                return false;
            }
            leftUp--;
            rightUp++;

        }
        return true;
    }

    /**
     * 打印出一个二维矩阵
     */
    public static void printQueens(int[] result){
        for (int row = 0;row<8;row++){
            for (int column=0;column<8;column++){
                if (result[row] == column){
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

}
